import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.*;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-25
 * Time: 16:28
 */
public class BinaryTree {
    //静态内部类，不用实例化对象，直接利用类名调用
    static class TreeNode{
        public int val;
        public TreeNode  left;
        public TreeNode  right;

        public TreeNode(int val){
            this.val=val;
        }
    }
    //定义根节点
    public TreeNode root;

    //查找对应值
    public TreeNode search(int key){
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val==key){
                return cur;
            }else if(key<cur.val){
                cur=cur.left;//去左子树找
            }else{
                cur=cur.right;//去右子树找
            }
        }
        return null;//找不到
    }

    //迭代版插入操作，插入一个节点
    public void insertTreeNor(int val){
        if(root==null){
            root=new TreeNode(val);
            return ;
        }
        TreeNode p=null;//用于记录下一个节点为空时的上一个节点
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val<val){
                p=cur;//先记录本节点
                cur=cur.right;//往右边走
            }else{
                p=cur;
                cur=cur.left;
            }
        }
        //当cur为空时，插入节点
        TreeNode node=new TreeNode(val);
        if(p.val<val){
            p.right=node;
        }else{
            p.left=node;
        }
    }

    //递归版插入操作
    public void insertTree(TreeNode root,int val){//无返回值类型
        if(root==null) new TreeNode(val);
        if(root.val>val){
            insertTree(root.left,val);
        }else{
            insertTree(root.right,val);
        }

    }

    /*public TreeNode insertTree1(TreeNode root,int val){//返回节点类型
        if(root==null)
            return new TreeNode(val);//为空时，构造新的节点为根节点
        else if(root.val>val){
            root.left=insertTree1(root.left,val);//在节点左边插入一个节点，返回值是要插入的节点
        }else{
            root.right=insertTree1(root.right,val);//在节点右边插入一个节点
        }
        return root;//返回根节点
    }*/


    //删除操作
    public void remove(int key){
        TreeNode parent=null;
        TreeNode cur=root;
        //找要删除值的对应的节点
        while(cur!=null){
            if(cur.val<key){
                parent=cur;
                cur=cur.right;//往右边走
            }else if(cur.val>key){
                parent=cur;
                cur=cur.left;
            }else{
                removeNode(parent,cur);
                return ;
            }
        }
    }

    public void removeNode(TreeNode parent,TreeNode cur){
        //三种情况，左为空，右为空，左右都不为空
        if(cur.left==null){
            //三种情况，是根，在根的左边，在根的右边
            if(cur==root){
                root=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;
            }else{
                parent.right=cur.right;
            }
        }else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }else if(cur==parent.left){
                parent.left=cur.left;
            }else{
                parent.right=cur.left;
            }
        }else{//左右两边都不为空
            TreeNode targetParent=cur;
            TreeNode target=cur.right;//去右边子树找最小的
            while(target.left!=null){
                targetParent=target;
                target=target.left;//一直往左走，直到找到最小的
            }
            //此时target左树为空，那么target此时就是最小的，找到了最小的值，赋值给cur
            cur.val=target.val;
            //找到后删除刚刚的最小的节点，有两种情况
            if(targetParent.left==target){
                targetParent.left=target.right;//删除
            }else{
                targetParent.right=target.right;
            }
        }
    }

    //中序遍历，用于打印搜索树
    public void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    //前序遍历，用于打印搜索树
    public void preorder(TreeNode root){
        if(root==null){
            return ;
        }
        System.out.print(root.val+" ");
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {

    }
}

